// @FileName  :graphSearch.c
// @Time      :2024/5/24 14:12
// @Author    :YKW
//# include <bits/stdc++.h>
//using namespace std;
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <string.h>
# include <stdlib.h>

int n, m, k, edges[100], cnt;

int cmp(const void *x, const void *y) {
    return (*(int *) x) - (*(int *) y);
}

struct node {
    int num, edge[100], flag;
} seq[150];

void dfs(int num) {
    seq[num].flag = 1;
    printf("%d ", num);
    for (int i = 0; i < seq[num].num; i++) {
        if (seq[seq[num].edge[i]].flag == 1) continue;
        dfs(seq[num].edge[i]);
    }
}

void bfs(int num) {
    int st = 0, ed = 0, q[200];
    q[ed++] = num;
    while (st < ed) {
        int cur=q[st];
        for (int i = 0; i < seq[cur].num; i++) {
            if (seq[seq[cur].edge[i]].flag == 0) {
                seq[seq[cur].edge[i]].flag = 1;
                q[ed++] = seq[cur].edge[i];
            }
        }
        printf("%d ", q[st++]);
    }
}

void undo() {
    printf("\n");
    for (int i = 0; i < n; i++)
        seq[i].flag = 0;
    seq[0].flag = 1;
}

int main() {
    setbuf(stdout, NULL);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        seq[a].edge[seq[a].num++] = b;
        seq[b].edge[seq[b].num++] = a;
    }
    scanf("%d", &k);
    for (int i = 0; i < n; i++)
        qsort(seq[i].edge, seq[i].num, sizeof(int), cmp);
    undo();
    dfs(0);
    undo();
    bfs(0);
    undo();
    seq[k].flag = 1;
    dfs(0);
    undo();
    seq[k].flag = 1;
    bfs(0);
}
/*
9 10
0 1
0 2
1 4
1 3
1 8
8 6
3 6
7 2
7 5
5 2
3
 */